package kr.hkit.powerjava.algorithm;

import java.util.Arrays;

public class BinarySearch{

	private int[] arr;//숫자를 찾을 배열
	private int searchKey;//찾는 숫자
	private int mid, leftidx, rightidx;//인덱스 정보

	public BinarySearch(int[] arr, int searchKey) {
		this.arr = arr;
		this.searchKey = searchKey;
	}

	public int getSearchKey() {
		return searchKey;
	}

	public void setSearchKey(int searchKey) {
		this.searchKey = searchKey;
	}
	
	public void binary(){
		leftidx = 0;//가장 왼쪽은 항상 인덱스가 0
		rightidx = arr.length-1;//(길이-1)이 마지막 인덱스
		
		Arrays.sort(arr);//binary searching은 항상 정렬을 기본으로 한다
		
		while(rightidx >= leftidx){//왼쪽인덱스가 오른쪽인덱스보다 크다면 검색 할 만큼 했다는 의미
			mid = (int)((leftidx+rightidx)/2);//가운데 점 잡아주고
			if(isSame(mid)){//중간점의 값과 찾는 숫자가 같다면
				System.out.println(searchKey + " Found");//찾았고
				break;									//그만도세요
			}else{
				compare();	//숫자를 비교해서 범위를 좁히러 갑시다
			}
		}
		if(rightidx < leftidx && !isSame(mid)){//배열 돌만큼 다 돌았지만 값을 찾지 못했다
			System.out.println(searchKey + " Not-Found");//그런 수는 배열에 없다
		}
	}

	private boolean isSame(int mid){//mid인덱스로 찾는 숫자랑 비교
		return arr[mid] == searchKey;
	}
	
	private void compare(){
		if(arr[mid] > searchKey){//중간값보다 찾는 숫자가 작다면
			rightidx = mid;//왼쪽을 검색합시다
		}else{//중간값보다 찾는 숫자가 크니까
			leftidx = mid+1;//오른쪽을 검색합시다
		}
	}
	
	public void prnArr(){
		for(int a: arr){
			System.out.print(a + " ");
		}
		System.out.println();
	}
}
